#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:

	template<class T>
	class UnionFindSet
	{
	public:
		UnionFindSet(int n)
			:_ufs(n, -1)
		{}

		void Union(int x, int y)
		{
			int root1 = FindRoot(x);
			int root2 = FindRoot(y);

			if (root1 == root2)
				return;

			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;

		}

		int FindRoot(int x)
		{
			int parent = x;
			while (_ufs[parent] >= 0)
			{
				parent = _ufs[parent];
			}

			return parent;
		}

		bool Inset(int x, int y)
		{
			return FindRoot(x) == FindRoot(y);
		}

		size_t Size()
		{
			size_t num = 0;
			for (int i = 0; i < _ufs.size(); i++)
			{
				if (_ufs[i] < 0)
					num++;
			}

			return num;
		}

	private:
		vector<int> _ufs;
	};

	bool equationsPossible(vector<string>& equations) {
		UnionFindSet<int> ufs(26);


		for (int i = 0; i < equations.size(); i++)
		{
			if (equations[i][1] == '=')
			{
				int x = equations[i][0] - 'a';
				int y = equations[i][3] - 'a';
				ufs.Union(x, y);
			}
		}

		for (int i = 0; i < equations.size(); i++)
		{
			if (equations[i][1] == '!')
			{
				int x = equations[i][0] - 'a';
				int y = equations[i][3] - 'a';
				if (ufs.Inset(x, y))
				{
					return false;
				}
			}
		}

		return true;

	}

};